package com.test.leetcode;

/**
 * https://leetcode.cn/problems/minimum-path-sum/description/
 * @author sujiafa
 * @date 2025/4/10
 */
public class n64_最小路径和 {

    public int minPathSum(int[][] grid) {

        // 线性DP知识二例题
        // 定义状态dp[i][j]为从位置(0,0)到位置(i,j)的最小路径和
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int j = 1; j < cols; j++) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }

        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                // 当前位置(i,j)只能从左侧位置(i,j-1)或者上方位置(i-1,j)到达。为了使得从左上角到达(i,j)位置的最
                // 小路径和最小，应从(i,j-1)位置和(i-1,j)位置选择路径和最小的位置达到(i,j)
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[rows - 1][cols - 1];
    }
}
